package com.binaryTree;

import java.util.LinkedList;
import java.util.Queue;

public class FindBottomLeftTreeValue0302_513 {

    //层序遍历
    public int findBottomLeftValue0(TreeNode root) {
        if(root == null) return 0;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        int res = root.val;
        while (!que.isEmpty()){
            int len = que.size();
            res = que.peek().val;
            while (len > 0){
                TreeNode node = que.poll();
                if(node.left != null) que.offer(node.left);
                if(node.right != null) que.offer(node.right);

                len--;
            }
        }
        return res;
    }

    //递归
    private int Deep = -1; //全局变量，记录最大深度
    private int value = 0;
    public int findBottomLeftValue(TreeNode root) {
        value = root.val;
        findLeftValue(root,0);
        return value;
    }

    private void findLeftValue(TreeNode root, int deep) {
        if(root == null) return;
        if(root.left == null && root.right == null) {
            if (deep > Deep){
                value = root.val;
                Deep = deep;
            }
        }
        if(root.left != null) findLeftValue(root.left, deep+1);
        if(root.right != null) findLeftValue(root.right, deep+1);
    }
}
